1. Field of the Invention
The invention relates to a method and a device for acquiring a code phase shift, more particularly to a method and a device for acquiring the code phase shift between pseudo random (PN) sequences.
2. Description of the Related Art
In a general signal processing system, a phase shift between a pseudo-random (PN) input sequence and a reference sequence is useful in many aspects, such as signal synchronization and data analysis.
In order to obtain the phase shift, the cross-correlation between the input sequence with a current phase and the reference sequence is first obtained. The phase of the input sequence is subsequently varied, and a group of cross-correlations associated with different phases of the input sequence are obtained accordingly. A peak cross-correlation that has a greatest magnitude is selected from the aforementioned group, and the phase difference between the reference sequence and the phase of the input sequence that results in the peak cross-correlation is the desired phase shift.
Conventionally, the cross-correlations are computed using convolution theory, computation of which is not practical in time-domain because of the numerous multiplication and integration computations involved. According to the convolution theorem, convolution in one domain (e.g., time domain) equals point-wise multiplication in the other domain (e.g., frequency domain). Therefore, Fast Fourier Transformation (FFT) is used for transforming the sequences from the time domain to the frequency domain, so as to eliminate the requirement of integration computation.
However, FFT has a drawback in that FFT involves complex multiplication and addition, resulting in a computational complexity of N·log2N when processing a sequence of length N. That is, as the length N of the sequence increases, computational load of FFT for processing the sequence is increased at an even faster rate. As a result, FFT may be unsuitable in a signal processing system that involves a sequence with a very large length N, such as in a global navigation satellite system (GNSS) or a global positioning system (GPS).